package 题目集.滑动窗口;

import org.junit.Test;

/**
 * https://leetcode.cn/problems/shortest-subarray-with-or-at-least-k-i/description/?envType=daily-question&envId=2025-01-16
 * 给你一个 非负 整数数组 nums 和一个整数 k 。
 * 如果一个数组中所有元素的按位或运算 OR 的值 至少 为 k ，那么我们称这个数组是 特别的 。
 * 请你返回 nums 中 最短特别非空子数组
 * 的长度，如果特别子数组不存在，那么返回 -1 。
 */
public class demo03_或值至少K的最短子数组I {

    /**
     * 暴力思路：枚举所有区间，时间复杂度n^2
     */

    /**
     * 滑动窗口思路：这题很明显具有单调性，但难点在于左缩时如何求逆运算。
     * 其实也好弄，可以记录二进制中每个位置有多少个1，左缩的时候把这些1给去掉，再求一次二进制的值即可
     */
    int maxn = 50;

    int[] arr = new int[6]; //范围小，6位就够了

    int val = 0;

    public int minimumSubarrayLength(int[] nums, int k) {
        int res = Integer.MAX_VALUE;
        for (int l = 0, r = 0; r < nums.length; r++) {
            if (nums[r] >= k) return 1;
            or(nums[r]);
            while (val >= k && l <= r) {
                res = Math.min(res, r - l + 1);
                unOr(nums[l++]);
            }
        }
        return res == Integer.MAX_VALUE ? -1 : res;
    }

    /**
     * 或运算
     *
     * @param v
     * @return
     */
    public void or(int v) {
        val |= v;
        for (int i = 0; v > 0; i++, v = v >> 1) {
            arr[i] += v & 1;
        }
    }

    /**
     * 或运算求逆
     *
     * @param v
     * @return
     */
    public void unOr(int v) {
        for (int i = 0, x = 1; v > 0; i++, x = x << 1, v = v >> 1) {
            arr[i] -= v & 1;
            if (arr[i] == 0) {
                val &= ~x;
            }
        }
    }

    @Test
    public void test() {
        int[] arr = {2, 1, 8};
        System.out.println(minimumSubarrayLength(arr, 10));
    }
}
